package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 *
 * <p>每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 *
 * <p>这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 *
 * <p>返回一个由上述 k 部分组成的数组。
 *
 * <p>  示例 1：
 *
 * <p>输入：head = [1,2,3], k = 5 输出：[[1],[2],[3],[],[]] 解释： 第一个元素 output[0] 为 output[0].val = 1
 * ，output[0].next = null 。 最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test725 {

    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] result;
        List<ListNode> list = new ArrayList<>();
        ListNode pre = head;
        while (pre != null){
            list.add(pre);
            pre = pre.next;
        }
        int size = list.size();
        if (size <= k ){
            result = new ListNode[k];
            for (int i =0;i<size;i++){
                ListNode listNode = list.get(i);
                result[i] = listNode;
                listNode.next = null;
            }
            return result;
        }else {
            result = new ListNode[k];
            int remainder = size % k; // 余数
            int temp = 0;
            int num = size / k;
            for (int i =0;i<k;i++){
                if (remainder>0){
                    result[i] = list.get(temp);
                    ListNode listNode = list.get((i + 1) * (num + 1) - 1);
                    listNode.next = null;
                    temp = (num+1) * (i+1);
                }else {
                    result[i] = list.get(temp);
                    list.get(temp+num-1).next = null;
                    temp+=num;
                }
                remainder--;
            }
            return result;
        }
    }
}


class Demo725{
  public static void main(String[] args) {
    ListNode head = new ListNode(-1);
    ListNode tail = head;
    int k = 3;
    for (int i = 1;i<=7;i++){
        ListNode listNode = new ListNode(i);
        tail.next = listNode;
        tail = listNode;
    }
    System.out.println();
    Test725 t = new Test725();
    ListNode[] listNodes = t.splitListToParts(head.next, k);
    for (int i =0;i<listNodes.length;i++){
        ListNode pre = listNodes[i];
        while (pre != null){
            System.out.printf(pre.val+",");
            pre = pre.next;
        }
      System.out.println();
    }
  }
}